{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "Z12nIL0GmtKF"
   },
   "source": [
    "## Machine learning on Social Netowrk Graphs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "executionInfo": {
     "elapsed": 2015,
     "status": "ok",
     "timestamp": 1616871368226,
     "user": {
      "displayName": "Aldo Marzullo",
      "photoUrl": "https://lh3.googleusercontent.com/a-/AOh14GjBD_mZewcZ8LCqkD20Nku4DR5OCGFqYkxawoUjgg=s64",
      "userId": "17245895923239449231"
     },
     "user_tz": -60
    },
    "id": "Plnw0bRc_Mks"
   },
   "outputs": [],
   "source": [
    "import os\n",
    "import math\n",
    "import numpy as np\n",
    "import networkx as nx\n",
    "import matplotlib.pyplot as plt\n",
    "%matplotlib inline\n",
    "\n",
    "default_edge_color = 'gray'\n",
    "default_node_color = '#407cc9'\n",
    "enhanced_node_color = '#f5b042'\n",
    "enhanced_edge_color = '#cc2f04'"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "g-X4DgHfmzko"
   },
   "source": [
    "In this chapter we will focus on using the techniques outlined in previous chapters to analyze the most-common example of nowadays graphs: Social Networks. In particular we will apply the techniques outlined in previous chapters to investigate the topological properties of the networks, such as \n",
    "1. identifying relevant communities as well as \n",
    "2. identifying particularly important nodes in the network. \n",
    "\n",
    "We will then use node embeddings to leverage on the power of topological information for different tasks, such as link prediction (as a potential recommendation engine for new friends) "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "v8L1V6CKqv6_"
   },
   "source": [
    "#### Dowload the dataset\n",
    "\n",
    "First, we need to download the dataset. We will be using the [SNAP Facebook social graph](http://snap.stanford.edu). The dataset was created by collection Facebook user information from survey participants.  More in detail, 10 ego-networks were created from ten users. Each user was asked to identify all the circles (list of friends) to which their friends belong. Then, all the \"ego-network\" were combined in a single graph."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "executionInfo": {
     "elapsed": 3063,
     "status": "ok",
     "timestamp": 1616871375254,
     "user": {
      "displayName": "Aldo Marzullo",
      "photoUrl": "https://lh3.googleusercontent.com/a-/AOh14GjBD_mZewcZ8LCqkD20Nku4DR5OCGFqYkxawoUjgg=s64",
      "userId": "17245895923239449231"
     },
     "user_tz": -60
    },
    "id": "1F-dlWqNGaF8",
    "outputId": "c422ddf8-3bad-45ae-e437-67d94bc8d480"
   },
   "outputs": [],
   "source": [
    "!wget http://snap.stanford.edu/data/facebook_combined.txt.gz\n",
    "!wget http://snap.stanford.edu/data/facebook.tar.gz\n",
    "!gzip -d facebook_combined.txt.gz\n",
    "!tar -xf facebook.tar.gz"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "Vye1SbKAnI_A"
   },
   "source": [
    "### Overview of the Dataset"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "_xRLZ3EmrRtW"
   },
   "source": [
    "The code above downloads two main files:\n",
    "*   a text file containing the edge list of the graph. The graph is actually created\n",
    "*   an archive containing a folder (\"facebook\") with all the information related to each ego-network\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "executionInfo": {
     "elapsed": 572,
     "status": "ok",
     "timestamp": 1615730514627,
     "user": {
      "displayName": "Aldo Marzullo",
      "photoUrl": "https://lh3.googleusercontent.com/a-/AOh14GjBD_mZewcZ8LCqkD20Nku4DR5OCGFqYkxawoUjgg=s64",
      "userId": "17245895923239449231"
     },
     "user_tz": -60
    },
    "id": "0u_P2c3T-bc5",
    "outputId": "bb59b58d-ecf4-45ae-f867-102c84bc09b1"
   },
   "outputs": [],
   "source": [
    "# check the downloaded content\n",
    "!ls"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "executionInfo": {
     "elapsed": 637,
     "status": "ok",
     "timestamp": 1615730516414,
     "user": {
      "displayName": "Aldo Marzullo",
      "photoUrl": "https://lh3.googleusercontent.com/a-/AOh14GjBD_mZewcZ8LCqkD20Nku4DR5OCGFqYkxawoUjgg=s64",
      "userId": "17245895923239449231"
     },
     "user_tz": -60
    },
    "id": "Uno8xGcQ-jjd",
    "outputId": "02b5d01a-4e08-4d95-f36c-7251248b3294"
   },
   "outputs": [],
   "source": [
    "# take a look at the first lines of the edge list\n",
    "!head facebook_combined.txt"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "-J68AHFLsLP6"
   },
   "source": [
    "We can now proceed loading the combined network using networkx. We will also load the nodeId of the 10 \"ego-user\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "executionInfo": {
     "elapsed": 923,
     "status": "ok",
     "timestamp": 1616871380640,
     "user": {
      "displayName": "Aldo Marzullo",
      "photoUrl": "https://lh3.googleusercontent.com/a-/AOh14GjBD_mZewcZ8LCqkD20Nku4DR5OCGFqYkxawoUjgg=s64",
      "userId": "17245895923239449231"
     },
     "user_tz": -60
    },
    "id": "peTKyoylGUuS"
   },
   "outputs": [],
   "source": [
    "G = nx.read_edgelist(\"facebook_combined.txt\", create_using=nx.Graph(), nodetype=int)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "executionInfo": {
     "elapsed": 626,
     "status": "ok",
     "timestamp": 1615730522807,
     "user": {
      "displayName": "Aldo Marzullo",
      "photoUrl": "https://lh3.googleusercontent.com/a-/AOh14GjBD_mZewcZ8LCqkD20Nku4DR5OCGFqYkxawoUjgg=s64",
      "userId": "17245895923239449231"
     },
     "user_tz": -60
    },
    "id": "ssuI-8mvibIj",
    "outputId": "44e5daa6-07f3-47ec-8bc7-1d3fba54d0ee"
   },
   "outputs": [],
   "source": [
    "print(nx.info(G))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "executionInfo": {
     "elapsed": 787,
     "status": "ok",
     "timestamp": 1616871385179,
     "user": {
      "displayName": "Aldo Marzullo",
      "photoUrl": "https://lh3.googleusercontent.com/a-/AOh14GjBD_mZewcZ8LCqkD20Nku4DR5OCGFqYkxawoUjgg=s64",
      "userId": "17245895923239449231"
     },
     "user_tz": -60
    },
    "id": "QpouOy0bYTzR"
   },
   "outputs": [],
   "source": [
    "# Each file in the \"facebook\" directory is named as nodeId.format\n",
    "# where nodeId is the id of an ego-user and format is the format of the file\n",
    "ego_nodes = set([int(name.split('.')[0]) for name in os.listdir(\"facebook/\")])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "bg6hTAj_tNDA"
   },
   "source": [
    "Let's visualize the network for a deeper understanding"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "id": "poIVgKmCHFw3"
   },
   "outputs": [],
   "source": [
    "#Create network layout for visualizations\n",
    "spring_pos = nx.spring_layout(G)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 248
    },
    "executionInfo": {
     "elapsed": 2028,
     "status": "ok",
     "timestamp": 1615730581807,
     "user": {
      "displayName": "Aldo Marzullo",
      "photoUrl": "https://lh3.googleusercontent.com/a-/AOh14GjBD_mZewcZ8LCqkD20Nku4DR5OCGFqYkxawoUjgg=s64",
      "userId": "17245895923239449231"
     },
     "user_tz": -60
    },
    "id": "4AqPky9FsP7Y",
    "outputId": "062d5b31-6091-4df7-b3e5-5914ef14aaa2"
   },
   "outputs": [],
   "source": [
    "plt.axis(\"off\")\n",
    "nx.draw_networkx(G, pos=spring_pos, node_color=default_node_color, edge_color=default_edge_color, with_labels=False, node_size=35)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "2z2PCthzneat"
   },
   "source": [
    "### Network Analysis"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "id": "pRnhOeSYsHn4"
   },
   "outputs": [],
   "source": [
    "def draw_metric(G, dct, spring_pos):\n",
    "  \"\"\" draw the graph G using the layout spring_pos.\n",
    "      The top 10 nodes w.r.t. values in the dictionary dct\n",
    "      are enhanced in the visualization \"\"\"\n",
    "  top = 10\n",
    "  max_nodes =  sorted(dct.items(), key = lambda v: -v[1])[:top]\n",
    "  \n",
    "  max_keys = [key for key,_ in max_nodes]\n",
    "  max_vals = [val*300 for _, val in max_nodes]\n",
    "\n",
    "  plt.axis(\"off\")\n",
    "  \n",
    "  nx.draw_networkx(G, \n",
    "                   pos=spring_pos, \n",
    "                   cmap='Blues', \n",
    "                   edge_color=default_edge_color,\n",
    "                   node_color=default_node_color, \n",
    "                   node_size=3,\n",
    "                   alpha=0.4, \n",
    "                   with_labels=False)\n",
    "  \n",
    "  nx.draw_networkx_nodes(G, \n",
    "                         pos=spring_pos, \n",
    "                         nodelist=max_keys, \n",
    "                         node_color=enhanced_edge_color,\n",
    "                         node_size=max_vals)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "executionInfo": {
     "elapsed": 628,
     "status": "ok",
     "timestamp": 1615730796465,
     "user": {
      "displayName": "Aldo Marzullo",
      "photoUrl": "https://lh3.googleusercontent.com/a-/AOh14GjBD_mZewcZ8LCqkD20Nku4DR5OCGFqYkxawoUjgg=s64",
      "userId": "17245895923239449231"
     },
     "user_tz": -60
    },
    "id": "gPMC9VDyuF5F",
    "outputId": "c467e5de-3e8d-4f5c-f954-4f6758bf4ac6"
   },
   "outputs": [],
   "source": [
    "# betweenness centrality\n",
    "bC = nx.betweenness_centrality(G)\n",
    "np.mean(list(bC.values()))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 248
    },
    "executionInfo": {
     "elapsed": 2515,
     "status": "ok",
     "timestamp": 1615730862198,
     "user": {
      "displayName": "Aldo Marzullo",
      "photoUrl": "https://lh3.googleusercontent.com/a-/AOh14GjBD_mZewcZ8LCqkD20Nku4DR5OCGFqYkxawoUjgg=s64",
      "userId": "17245895923239449231"
     },
     "user_tz": -60
    },
    "id": "8uwzyBU8DJPQ",
    "outputId": "412d94cc-8b6a-4e34-f665-78ce11dd3e24"
   },
   "outputs": [],
   "source": [
    "draw_metric(G,bC,spring_pos)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "executionInfo": {
     "elapsed": 41093,
     "status": "ok",
     "timestamp": 1615730944044,
     "user": {
      "displayName": "Aldo Marzullo",
      "photoUrl": "https://lh3.googleusercontent.com/a-/AOh14GjBD_mZewcZ8LCqkD20Nku4DR5OCGFqYkxawoUjgg=s64",
      "userId": "17245895923239449231"
     },
     "user_tz": -60
    },
    "id": "wXbYnUjisJjq",
    "outputId": "2087e3f7-c47a-42dc-d2a4-f8050dd817fd"
   },
   "outputs": [],
   "source": [
    "# global efficiency\n",
    "gE = nx.global_efficiency(G)\n",
    "print(gE)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "executionInfo": {
     "elapsed": 3097,
     "status": "ok",
     "timestamp": 1615730995901,
     "user": {
      "displayName": "Aldo Marzullo",
      "photoUrl": "https://lh3.googleusercontent.com/a-/AOh14GjBD_mZewcZ8LCqkD20Nku4DR5OCGFqYkxawoUjgg=s64",
      "userId": "17245895923239449231"
     },
     "user_tz": -60
    },
    "id": "-rTdO9YrsbqP",
    "outputId": "854d3db6-d42e-4f5e-ea77-30840164f6af"
   },
   "outputs": [],
   "source": [
    "# average clustering\n",
    "aC = nx.average_clustering(G)\n",
    "print(aC)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "executionInfo": {
     "elapsed": 635,
     "status": "ok",
     "timestamp": 1615730998455,
     "user": {
      "displayName": "Aldo Marzullo",
      "photoUrl": "https://lh3.googleusercontent.com/a-/AOh14GjBD_mZewcZ8LCqkD20Nku4DR5OCGFqYkxawoUjgg=s64",
      "userId": "17245895923239449231"
     },
     "user_tz": -60
    },
    "id": "94viGU4vserg",
    "outputId": "05b8e669-e338-4943-88ff-5ece3ce55a8c"
   },
   "outputs": [],
   "source": [
    "# degree centrality\n",
    "deg_C = nx.degree_centrality(G)\n",
    "np.mean(list(deg_C.values()))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 248
    },
    "executionInfo": {
     "elapsed": 2072,
     "status": "ok",
     "timestamp": 1615731014642,
     "user": {
      "displayName": "Aldo Marzullo",
      "photoUrl": "https://lh3.googleusercontent.com/a-/AOh14GjBD_mZewcZ8LCqkD20Nku4DR5OCGFqYkxawoUjgg=s64",
      "userId": "17245895923239449231"
     },
     "user_tz": -60
    },
    "id": "L73effhYiPYp",
    "outputId": "48bfad8c-3581-48dc-cd22-4c4caa088790"
   },
   "outputs": [],
   "source": [
    "draw_metric(G,deg_C,spring_pos)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "executionInfo": {
     "elapsed": 41617,
     "status": "ok",
     "timestamp": 1615731059755,
     "user": {
      "displayName": "Aldo Marzullo",
      "photoUrl": "https://lh3.googleusercontent.com/a-/AOh14GjBD_mZewcZ8LCqkD20Nku4DR5OCGFqYkxawoUjgg=s64",
      "userId": "17245895923239449231"
     },
     "user_tz": -60
    },
    "id": "vLp2CBJHtC1d",
    "outputId": "e5e9c70a-1327-4590-d4c4-049e0484115f"
   },
   "outputs": [],
   "source": [
    "# closeness centrality\n",
    "clos_C = nx.closeness_centrality(G)\n",
    "np.mean(list(clos_C.values()))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 248
    },
    "executionInfo": {
     "elapsed": 257027,
     "status": "ok",
     "timestamp": 1614955028566,
     "user": {
      "displayName": "Aldo Marzullo",
      "photoUrl": "https://lh3.googleusercontent.com/a-/AOh14GjBD_mZewcZ8LCqkD20Nku4DR5OCGFqYkxawoUjgg=s64",
      "userId": "17245895923239449231"
     },
     "user_tz": -60
    },
    "id": "jjVxMxbWi23s",
    "outputId": "709444e2-13b5-473d-b0f1-f920889be174"
   },
   "outputs": [],
   "source": [
    "draw_metric(G,clos_C,spring_pos)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "executionInfo": {
     "elapsed": 1498,
     "status": "ok",
     "timestamp": 1615731119603,
     "user": {
      "displayName": "Aldo Marzullo",
      "photoUrl": "https://lh3.googleusercontent.com/a-/AOh14GjBD_mZewcZ8LCqkD20Nku4DR5OCGFqYkxawoUjgg=s64",
      "userId": "17245895923239449231"
     },
     "user_tz": -60
    },
    "id": "MQOah_yDtbaW",
    "outputId": "7a449548-ba12-41be-cd93-6a3c0f1beb88"
   },
   "outputs": [],
   "source": [
    "# assortativity\n",
    "assortativity = nx.degree_pearson_correlation_coefficient(G)\n",
    "assortativity"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "executionInfo": {
     "elapsed": 5142,
     "status": "ok",
     "timestamp": 1615731126175,
     "user": {
      "displayName": "Aldo Marzullo",
      "photoUrl": "https://lh3.googleusercontent.com/a-/AOh14GjBD_mZewcZ8LCqkD20Nku4DR5OCGFqYkxawoUjgg=s64",
      "userId": "17245895923239449231"
     },
     "user_tz": -60
    },
    "id": "axqLxhKXtoqF",
    "outputId": "118e10dc-f058-47c6-aa5a-5db66d6a5cef"
   },
   "outputs": [],
   "source": [
    "t = nx.transitivity(G)\n",
    "t"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "id": "_KKwGKCUARdb"
   },
   "outputs": [],
   "source": [
    "#import networkx.algorithms.community as nx_comm\n",
    "#nx_comm.modularity(G, nx_comm.label_propagation_communities(G))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "5NeaSTApuLyZ"
   },
   "source": [
    "#### Community detection\n",
    "In the following cells we will automatically detect communities using infromation from the network topology"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 418
    },
    "executionInfo": {
     "elapsed": 4197,
     "status": "ok",
     "timestamp": 1615731133872,
     "user": {
      "displayName": "Aldo Marzullo",
      "photoUrl": "https://lh3.googleusercontent.com/a-/AOh14GjBD_mZewcZ8LCqkD20Nku4DR5OCGFqYkxawoUjgg=s64",
      "userId": "17245895923239449231"
     },
     "user_tz": -60
    },
    "id": "KP54IveMbNLD",
    "outputId": "39f42abd-9cf5-4755-de44-b9f7b4600d4b"
   },
   "outputs": [],
   "source": [
    "import community\n",
    "\n",
    "parts = community.best_partition(G)\n",
    "values = [parts.get(node) for node in G.nodes()]\n",
    "\n",
    "for node in ego_nodes:\n",
    "  print(node, \"is in community number\", parts.get(node))\n",
    "  \n",
    "n_sizes = [5]*len(G.nodes())\n",
    "for node in ego_nodes:\n",
    "  n_sizes[node] = 250\n",
    "\n",
    "plt.axis(\"off\")\n",
    "nx.draw_networkx(G, pos=spring_pos, cmap=plt.get_cmap(\"Blues\"), edge_color=default_edge_color, node_color=values, node_size=n_sizes, with_labels=False)\n",
    "\n",
    "# enhance color and size of the ego-nodes\n",
    "nodes = nx.draw_networkx_nodes(G,spring_pos,ego_nodes,node_color=[parts.get(node) for node in ego_nodes])\n",
    "nodes.set_edgecolor(enhanced_node_color)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "sOJ0LIyLrnX8"
   },
   "source": [
    "### Ego-net analysis"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "ElSziksRue7G"
   },
   "source": [
    "Since the combined network we are analyzing is actually composed by 10 sub-networks (ego-networks), it's interesting to inspect all those subnetwork. In the following cells we will analyze the subnetwork of the ego-user \"0\"."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 248
    },
    "executionInfo": {
     "elapsed": 1318,
     "status": "ok",
     "timestamp": 1615731144363,
     "user": {
      "displayName": "Aldo Marzullo",
      "photoUrl": "https://lh3.googleusercontent.com/a-/AOh14GjBD_mZewcZ8LCqkD20Nku4DR5OCGFqYkxawoUjgg=s64",
      "userId": "17245895923239449231"
     },
     "user_tz": -60
    },
    "id": "shV3rrYbjkGy",
    "outputId": "23e0e823-56d7-4044-a490-a98d91978dc7"
   },
   "outputs": [],
   "source": [
    "G0 = nx.read_edgelist(\"facebook/0.edges\", create_using=nx.Graph(), nodetype=int)\n",
    "for node in G0.copy():\n",
    "  G0.add_edge(0,node)\n",
    "\n",
    "plt.axis(\"off\")\n",
    "pos_G0 = nx.spring_layout(G0)\n",
    "nx.draw_networkx(G0, pos=pos_G0, with_labels=False, node_size=35, edge_color=default_edge_color)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "4haXlOU3u3Wd"
   },
   "source": [
    "Nodes belonging to each subnetwork are stored in the \"facebook\" folder under the name nodeId.circles"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "id": "_mX4VNsvlPRb"
   },
   "outputs": [],
   "source": [
    "import pandas as pd\n",
    "circles = {}\n",
    "\n",
    "with open(\"facebook/0.circles\") as f_in:\n",
    "  line = f_in.readline().rstrip().split(\"\\t\")\n",
    "  while line and not '' in line:\n",
    "    circles[line[0]] = [int(v) for v in line[1:]]\n",
    "    line = f_in.readline().rstrip().split(\"\\t\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 248
    },
    "executionInfo": {
     "elapsed": 1256,
     "status": "ok",
     "timestamp": 1615731151095,
     "user": {
      "displayName": "Aldo Marzullo",
      "photoUrl": "https://lh3.googleusercontent.com/a-/AOh14GjBD_mZewcZ8LCqkD20Nku4DR5OCGFqYkxawoUjgg=s64",
      "userId": "17245895923239449231"
     },
     "user_tz": -60
    },
    "id": "W-TKkMJemhlv",
    "outputId": "2b1455cc-bb4b-4b5f-ecc5-a0411734184e"
   },
   "outputs": [],
   "source": [
    "node_colors = [0] * G0.number_of_nodes()\n",
    "count = 0\n",
    "for key in circles:\n",
    "  circle = circles[key]\n",
    "  for node in circle:\n",
    "    if node < G0.number_of_nodes():\n",
    "      node_colors[node] = count\n",
    "  count += 1\n",
    "\n",
    "nx.draw_networkx(G0, pos=pos_G0, with_labels=False, node_size=35, node_color=node_colors, edge_color=default_edge_color)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 248
    },
    "executionInfo": {
     "elapsed": 1259,
     "status": "ok",
     "timestamp": 1615731154782,
     "user": {
      "displayName": "Aldo Marzullo",
      "photoUrl": "https://lh3.googleusercontent.com/a-/AOh14GjBD_mZewcZ8LCqkD20Nku4DR5OCGFqYkxawoUjgg=s64",
      "userId": "17245895923239449231"
     },
     "user_tz": -60
    },
    "id": "MYtd8B9Atc1Y",
    "outputId": "bbe6645f-769c-4f94-f734-450871a0c3e4"
   },
   "outputs": [],
   "source": [
    "parts = community.best_partition(G0)\n",
    "values = [parts.get(node) for node in G0.nodes()]\n",
    "\n",
    "plt.axis(\"off\")\n",
    "nx.draw_networkx(G0, pos=pos_G0, cmap=plt.get_cmap(\"Blues\"), edge_color=default_edge_color, node_color=values, node_size=35, with_labels=False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "executionInfo": {
     "elapsed": 634,
     "status": "ok",
     "timestamp": 1615731157443,
     "user": {
      "displayName": "Aldo Marzullo",
      "photoUrl": "https://lh3.googleusercontent.com/a-/AOh14GjBD_mZewcZ8LCqkD20Nku4DR5OCGFqYkxawoUjgg=s64",
      "userId": "17245895923239449231"
     },
     "user_tz": -60
    },
    "id": "1fRxbnx9t958",
    "outputId": "218dbef6-4e29-4f14-b603-6bcdce7c8878"
   },
   "outputs": [],
   "source": [
    "# community found does not reflect the circles\n",
    "set(parts.values())\n",
    "len(circles)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "id": "qOho3z8Ew1yb"
   },
   "outputs": [],
   "source": [
    "# a node can be present in more than one list??\n",
    "for i in circles:\n",
    "  for j in circles:\n",
    "    if i != j:\n",
    "      for n1 in circles[i]:\n",
    "        for n2 in circles[j]:\n",
    "          if n1 == n2:\n",
    "            print(n1, 'present in ',i,'found in', j)\n",
    "            assert(False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "cellView": "form",
    "id": "oo535vsIy684"
   },
   "outputs": [],
   "source": [
    "#@title  \n",
    "nx.average_shortest_path_length(G0)\n",
    "nx.global_efficiency(G0)\n",
    "nx.average_clustering(G0)\n",
    "\n",
    "np.mean(list(nx.betweenness_centrality(G0).values()))\n",
    "np.mean(list(nx.closeness_centrality(G0).values()))\n",
    "np.mean(list(nx.degree_centrality(G0).values()))\n",
    "nx.degree_pearson_correlation_coefficient(G)\n",
    "nx.transitivity(G)\n",
    "\n",
    "import networkx.algorithms.community as nx_comm\n",
    "nx_comm.modularity(G, nx_comm.label_propagation_communities(G))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "c8peWeN9nh1m"
   },
   "source": [
    "### Embeddings for Supervised and Unsupervised Tasks "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "VkzdQmIhvNm6"
   },
   "source": [
    "We will now proceed with the actual machine learning task. In particular, we will perform an edge prediction task for the Facebook social graph."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "VGjBXR_JCXgA"
   },
   "source": [
    "#### parse node features\n",
    "\n",
    "As first, let's load all the features describing each node. This is not a straightforward process and requires a bit of codes, since each subnetwork contains it's own set of features, whose names and values are stored in different files. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "id": "baistC-ZdaRf"
   },
   "outputs": [],
   "source": [
    "# Adapted from https://github.com/jcatw/snap-facebook\n",
    "\n",
    "feat_file_name = \"feature_map.txt\"\n",
    "feature_index = {}  #numeric index to name\n",
    "inverted_feature_index = {} #name to numeric index\n",
    "network = nx.Graph()\n",
    "\n",
    "def parse_featname_line(line):\n",
    "  \"\"\" used to parse each line of the files containing feature names \"\"\"\n",
    "  line = line[(line.find(' '))+1:]  # chop first field\n",
    "  split = line.split(';')\n",
    "  name = ';'.join(split[:-1]) # feature name\n",
    "  index = int(split[-1].split(\" \")[-1]) #feature index\n",
    "  return index, name\n",
    "\n",
    "def load_features():\n",
    "  \"\"\" \n",
    "  parse each ego-network and creates two dictionaries:\n",
    "      - feature_index: maps numeric indices to names\n",
    "      - inverted_feature_index: maps names to numeric indices\n",
    "  \"\"\"\n",
    "  import glob\n",
    "  feat_file_name = 'tmp.txt'\n",
    "  # may need to build the index first\n",
    "  if not os.path.exists(feat_file_name):\n",
    "      feat_index = {}\n",
    "      # build the index from data/*.featnames files\n",
    "      featname_files = glob.iglob(\"facebook/*.featnames\")\n",
    "      for featname_file_name in featname_files:\n",
    "          featname_file = open(featname_file_name, 'r')\n",
    "          for line in featname_file:\n",
    "              # example line:\n",
    "              # 0 birthday;anonymized feature 376\n",
    "              index, name = parse_featname_line(line)\n",
    "              feat_index[index] = name\n",
    "          featname_file.close()\n",
    "      keys = feat_index.keys()\n",
    "      keys = sorted(keys)\n",
    "      out = open(feat_file_name,'w')\n",
    "      for key in keys:\n",
    "          out.write(\"%d %s\\n\" % (key, feat_index[key]))\n",
    "      out.close()\n",
    "\n",
    "  index_file = open(feat_file_name,'r')\n",
    "  for line in index_file:\n",
    "      split = line.strip().split(' ')\n",
    "      key = int(split[0])\n",
    "      val = split[1]\n",
    "      feature_index[key] = val\n",
    "  index_file.close()\n",
    "\n",
    "  for key in feature_index.keys():\n",
    "      val = feature_index[key]\n",
    "      inverted_feature_index[val] = key\n",
    "\n",
    "def parse_nodes(network, ego_nodes):\n",
    "  \"\"\"\n",
    "  for each nodes in the network assign the corresponding features \n",
    "  previously loaded using the load_features function\n",
    "  \"\"\"\n",
    "  # parse each node\n",
    "  for node_id in ego_nodes:\n",
    "      featname_file = open(f'facebook/{node_id}.featnames','r')\n",
    "      feat_file     = open(f'facebook/{node_id}.feat','r')\n",
    "      egofeat_file  = open(f'facebook/{node_id}.egofeat','r')\n",
    "      edge_file     = open(f'facebook/{node_id}.edges','r')\n",
    "\n",
    "      ego_features = [int(x) for x in egofeat_file.readline().split(' ')]\n",
    "\n",
    "      # Add ego node features\n",
    "      network.nodes[node_id]['features'] = np.zeros(len(feature_index))\n",
    "      \n",
    "      # parse ego node\n",
    "      i = 0\n",
    "      for line in featname_file:\n",
    "          key, val = parse_featname_line(line)\n",
    "          # Update feature value if necessary\n",
    "          if ego_features[i] + 1 > network.nodes[node_id]['features'][key]:\n",
    "              network.nodes[node_id]['features'][key] = ego_features[i] + 1\n",
    "          i += 1\n",
    "\n",
    "      # parse neighboring nodes\n",
    "      for line in feat_file:\n",
    "          featname_file.seek(0)\n",
    "          split = [int(x) for x in line.split(' ')]\n",
    "          node_id = split[0]\n",
    "          features = split[1:]\n",
    "\n",
    "          # Add node features\n",
    "          network.nodes[node_id]['features'] = np.zeros(len(feature_index))\n",
    "\n",
    "          i = 0\n",
    "          for line in featname_file:\n",
    "              key, val = parse_featname_line(line)\n",
    "              # Update feature value if necessary\n",
    "              if features[i] + 1 > network.nodes[node_id]['features'][key]:\n",
    "                  network.nodes[node_id]['features'][key] = features[i] + 1\n",
    "              i += 1\n",
    "          \n",
    "      featname_file.close()\n",
    "      feat_file.close()\n",
    "      egofeat_file.close()\n",
    "      edge_file.close()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "id": "2C3TwPVTdgeM"
   },
   "outputs": [],
   "source": [
    "# parse edge features and add them to the networkx nodes\n",
    "load_features()\n",
    "parse_nodes(G, ego_nodes)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "executionInfo": {
     "elapsed": 5210,
     "status": "ok",
     "timestamp": 1616266928734,
     "user": {
      "displayName": "Aldo Marzullo",
      "photoUrl": "https://lh3.googleusercontent.com/a-/AOh14GjBD_mZewcZ8LCqkD20Nku4DR5OCGFqYkxawoUjgg=s64",
      "userId": "17245895923239449231"
     },
     "user_tz": -60
    },
    "id": "oZIj_NqvVzmU",
    "outputId": "990227b3-7f01-4ef6-d036-9346c7ae5eca"
   },
   "outputs": [],
   "source": [
    "# check features has been correctly assigned\n",
    "G.nodes[0]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "7OHolBwscK2H"
   },
   "source": [
    "### Link prediction\n",
    "It's now time for machine learning.\n",
    "As first, we will be using stellargraph utility function to define a train and test set.\n",
    "More in detail, TODO"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 1000
    },
    "executionInfo": {
     "elapsed": 14891,
     "status": "ok",
     "timestamp": 1616871410804,
     "user": {
      "displayName": "Aldo Marzullo",
      "photoUrl": "https://lh3.googleusercontent.com/a-/AOh14GjBD_mZewcZ8LCqkD20Nku4DR5OCGFqYkxawoUjgg=s64",
      "userId": "17245895923239449231"
     },
     "user_tz": -60
    },
    "id": "Li-IypwmIW9V",
    "outputId": "580084bf-ff08-406d-b335-7f791b93e9fe"
   },
   "outputs": [],
   "source": [
    "!pip install stellargraph\n",
    "!pip install node2vec==0.3.3\n",
    "!pip install git+https://github.com/palash1992/GEM.git"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "executionInfo": {
     "elapsed": 9188,
     "status": "ok",
     "timestamp": 1616871428202,
     "user": {
      "displayName": "Aldo Marzullo",
      "photoUrl": "https://lh3.googleusercontent.com/a-/AOh14GjBD_mZewcZ8LCqkD20Nku4DR5OCGFqYkxawoUjgg=s64",
      "userId": "17245895923239449231"
     },
     "user_tz": -60
    },
    "id": "WsOOcDbfQifV",
    "outputId": "62d42e17-456d-4155-d91d-2bd39b79cde9"
   },
   "outputs": [],
   "source": [
    "from sklearn.model_selection import train_test_split\n",
    "from stellargraph.data import EdgeSplitter\n",
    "from stellargraph import StellarGraph\n",
    "\n",
    "edgeSplitter = EdgeSplitter(G) \n",
    "graph_test, samples_test, labels_test = edgeSplitter.train_test_split(p=0.1, method=\"global\", seed=24)\n",
    "\n",
    "edgeSplitter = EdgeSplitter(graph_test, G) \n",
    "graph_train, samples_train, labels_train = edgeSplitter.train_test_split(p=0.1, method=\"global\", seed=24)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "v0VscoAYx6_w"
   },
   "source": [
    "We will be comparing three different methods for predicting missing edges:\n",
    "- Method1: node2vec will be used to learn a node embedding. Such embeddings will be used to train a Random Forest classifier in a supervised manner\n",
    "- Method2: graphSAGE (with and without features) will be used for link prediction\n",
    "- Method3: hand-crafted features will be extracted and used to train a Random Forest classifier"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "P-8cKmYvwGeR"
   },
   "source": [
    "##### node2vec\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "executionInfo": {
     "elapsed": 209043,
     "status": "ok",
     "timestamp": 1616871720448,
     "user": {
      "displayName": "Aldo Marzullo",
      "photoUrl": "https://lh3.googleusercontent.com/a-/AOh14GjBD_mZewcZ8LCqkD20Nku4DR5OCGFqYkxawoUjgg=s64",
      "userId": "17245895923239449231"
     },
     "user_tz": -60
    },
    "id": "47_TddSbY0RN",
    "outputId": "d0eb3606-649c-417c-93a3-1bdf188006c6"
   },
   "outputs": [],
   "source": [
    "from node2vec import Node2Vec\n",
    "from node2vec.edges import HadamardEmbedder \n",
    "from stellargraph.data import EdgeSplitter \n",
    "\n",
    "node2vec = Node2Vec(graph_train) \n",
    "model = node2vec.fit() \n",
    "edges_embs = HadamardEmbedder(keyed_vectors=model.wv) \n",
    "train_embeddings = [edges_embs[str(x[0]),str(x[1])] for x in samples_train]\n",
    "\n",
    "edges_embs = HadamardEmbedder(keyed_vectors=model.wv) \n",
    "test_embeddings = [edges_embs[str(x[0]),str(x[1])] for x in samples_test]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "executionInfo": {
     "elapsed": 2806,
     "status": "ok",
     "timestamp": 1616871737132,
     "user": {
      "displayName": "Aldo Marzullo",
      "photoUrl": "https://lh3.googleusercontent.com/a-/AOh14GjBD_mZewcZ8LCqkD20Nku4DR5OCGFqYkxawoUjgg=s64",
      "userId": "17245895923239449231"
     },
     "user_tz": -60
    },
    "id": "HRq-PlbKcNvq",
    "outputId": "61f7c1e0-ed5d-49bf-e0b3-d0092f66beff"
   },
   "outputs": [],
   "source": [
    "from sklearn.ensemble import RandomForestClassifier \n",
    "from sklearn import metrics \n",
    "\n",
    "rf = RandomForestClassifier(n_estimators=10) \n",
    "rf.fit(train_embeddings, labels_train); \n",
    " \n",
    "y_pred = rf.predict(test_embeddings) \n",
    "print('Precision:', metrics.precision_score(labels_test, y_pred)) \n",
    "print('Recall:', metrics.recall_score(labels_test, y_pred)) \n",
    "print('F1-Score:', metrics.f1_score(labels_test, y_pred)) "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "ogTjZBNOwJ5y"
   },
   "source": [
    "##### graphSAGE"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "id": "R4Vk5GnxcWF2"
   },
   "outputs": [],
   "source": [
    "# graphSAGE no feats"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "id": "xK_GZyC5x6eE"
   },
   "outputs": [],
   "source": [
    "eye = np.eye(graph_train.number_of_nodes())\n",
    "fake_features = {n:eye[n] for n in G.nodes()}\n",
    "nx.set_node_attributes(graph_train, fake_features, \"fake\")\n",
    "\n",
    "eye = np.eye(graph_test.number_of_nodes())\n",
    "fake_features = {n:eye[n] for n in G.nodes()}\n",
    "nx.set_node_attributes(graph_test, fake_features, \"fake\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "executionInfo": {
     "elapsed": 808,
     "status": "ok",
     "timestamp": 1616266963123,
     "user": {
      "displayName": "Aldo Marzullo",
      "photoUrl": "https://lh3.googleusercontent.com/a-/AOh14GjBD_mZewcZ8LCqkD20Nku4DR5OCGFqYkxawoUjgg=s64",
      "userId": "17245895923239449231"
     },
     "user_tz": -60
    },
    "id": "Ntt0Mcpwy-G0",
    "outputId": "be140ce5-81f3-4ba7-df33-61a1a1b1e15a"
   },
   "outputs": [],
   "source": [
    "graph_train.nodes[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "id": "RGn0XYjexmy9"
   },
   "outputs": [],
   "source": [
    "from stellargraph.mapper import GraphSAGELinkGenerator\n",
    "\n",
    "batch_size = 64\n",
    "num_samples = [4, 4]\n",
    "\n",
    "sg_graph_train = StellarGraph.from_networkx(graph_train, node_features=\"fake\")\n",
    "sg_graph_test = StellarGraph.from_networkx(graph_test, node_features=\"fake\")\n",
    "\n",
    "train_gen = GraphSAGELinkGenerator(sg_graph_train, batch_size, num_samples)\n",
    "train_flow = train_gen.flow(samples_train, labels_train, shuffle=True, seed=24)\n",
    "\n",
    "test_gen = GraphSAGELinkGenerator(sg_graph_test, batch_size, num_samples)\n",
    "test_flow = test_gen.flow(samples_test, labels_test, seed=24)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "executionInfo": {
     "elapsed": 1253,
     "status": "ok",
     "timestamp": 1615731818925,
     "user": {
      "displayName": "Aldo Marzullo",
      "photoUrl": "https://lh3.googleusercontent.com/a-/AOh14GjBD_mZewcZ8LCqkD20Nku4DR5OCGFqYkxawoUjgg=s64",
      "userId": "17245895923239449231"
     },
     "user_tz": -60
    },
    "id": "Fv96b9CTwNaP",
    "outputId": "f39489eb-87c5-427c-b0a5-3d93aa25d0c4"
   },
   "outputs": [],
   "source": [
    "from stellargraph.layer import GraphSAGE, link_classification\n",
    "from tensorflow import keras\n",
    "\n",
    "layer_sizes = [20, 20]\n",
    "graphsage = GraphSAGE(\n",
    "    layer_sizes=layer_sizes, generator=train_gen, bias=True, dropout=0.3\n",
    ")\n",
    "\n",
    "x_inp, x_out = graphsage.in_out_tensors()\n",
    "\n",
    "prediction = link_classification(\n",
    "    output_dim=1, output_act=\"sigmoid\", edge_embedding_method=\"ip\"\n",
    ")(x_out)\n",
    "\n",
    "model = keras.Model(inputs=x_inp, outputs=prediction)\n",
    "\n",
    "model.compile(\n",
    "    optimizer=keras.optimizers.Adam(lr=1e-3),\n",
    "    loss=keras.losses.mse,\n",
    "    metrics=[\"acc\"],\n",
    ")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "executionInfo": {
     "elapsed": 294128,
     "status": "ok",
     "timestamp": 1615732114364,
     "user": {
      "displayName": "Aldo Marzullo",
      "photoUrl": "https://lh3.googleusercontent.com/a-/AOh14GjBD_mZewcZ8LCqkD20Nku4DR5OCGFqYkxawoUjgg=s64",
      "userId": "17245895923239449231"
     },
     "user_tz": -60
    },
    "id": "e-7QmsWQ3AVB",
    "outputId": "cf9996ad-ca77-4dbb-e6cd-1c8fa78d3d26"
   },
   "outputs": [],
   "source": [
    "epochs = 10\n",
    "history = model.fit(train_flow, epochs=epochs, validation_data=test_flow)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "executionInfo": {
     "elapsed": 15060,
     "status": "ok",
     "timestamp": 1615732132438,
     "user": {
      "displayName": "Aldo Marzullo",
      "photoUrl": "https://lh3.googleusercontent.com/a-/AOh14GjBD_mZewcZ8LCqkD20Nku4DR5OCGFqYkxawoUjgg=s64",
      "userId": "17245895923239449231"
     },
     "user_tz": -60
    },
    "id": "KIFkkB2K2HpW",
    "outputId": "1c60f2ab-6ce2-402d-877e-00486598e2e7"
   },
   "outputs": [],
   "source": [
    "from sklearn import metrics \n",
    "y_pred = np.round(model.predict(train_flow)).flatten()\n",
    "print('Precision:', metrics.precision_score(labels_train, y_pred)) \n",
    "print('Recall:', metrics.recall_score(labels_train, y_pred)) \n",
    "print('F1-Score:', metrics.f1_score(labels_train, y_pred)) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "executionInfo": {
     "elapsed": 14305,
     "status": "ok",
     "timestamp": 1615732149331,
     "user": {
      "displayName": "Aldo Marzullo",
      "photoUrl": "https://lh3.googleusercontent.com/a-/AOh14GjBD_mZewcZ8LCqkD20Nku4DR5OCGFqYkxawoUjgg=s64",
      "userId": "17245895923239449231"
     },
     "user_tz": -60
    },
    "id": "UwClat8v0avH",
    "outputId": "8ff471d3-301e-42ae-f4ef-35945e7d12c7"
   },
   "outputs": [],
   "source": [
    "y_pred = np.round(model.predict(test_flow)).flatten()\n",
    "print('Precision:', metrics.precision_score(labels_test, y_pred)) \n",
    "print('Recall:', metrics.recall_score(labels_test, y_pred)) \n",
    "print('F1-Score:', metrics.f1_score(labels_test, y_pred)) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "id": "7J8aSb7MfkQ1"
   },
   "outputs": [],
   "source": [
    "# graphSAGE + feats"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "id": "16lpkK-98W39"
   },
   "outputs": [],
   "source": [
    "sg_graph_train = StellarGraph.from_networkx(graph_train, node_features=\"features\")\n",
    "sg_graph_test = StellarGraph.from_networkx(graph_test, node_features=\"features\")\n",
    "\n",
    "train_gen = GraphSAGELinkGenerator(sg_graph_train, batch_size, num_samples)\n",
    "train_flow = train_gen.flow(samples_train, labels_train, shuffle=True, seed=24)\n",
    "\n",
    "test_gen = GraphSAGELinkGenerator(sg_graph_test, batch_size, num_samples)\n",
    "test_flow = test_gen.flow(samples_test, labels_test, seed=24)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "executionInfo": {
     "elapsed": 171414,
     "status": "ok",
     "timestamp": 1615732377339,
     "user": {
      "displayName": "Aldo Marzullo",
      "photoUrl": "https://lh3.googleusercontent.com/a-/AOh14GjBD_mZewcZ8LCqkD20Nku4DR5OCGFqYkxawoUjgg=s64",
      "userId": "17245895923239449231"
     },
     "user_tz": -60
    },
    "id": "9HFwHmGq8dCD",
    "outputId": "d3a73f88-c4eb-44a2-e303-e7b3530b4d58"
   },
   "outputs": [],
   "source": [
    "layer_sizes = [20, 20]\n",
    "graphsage = GraphSAGE(\n",
    "    layer_sizes=layer_sizes, generator=train_gen, bias=True, dropout=0.3\n",
    ")\n",
    "\n",
    "x_inp, x_out = graphsage.in_out_tensors()\n",
    "\n",
    "prediction = link_classification(\n",
    "    output_dim=1, output_act=\"sigmoid\", edge_embedding_method=\"ip\"\n",
    ")(x_out)\n",
    "\n",
    "model = keras.Model(inputs=x_inp, outputs=prediction)\n",
    "\n",
    "model.compile(\n",
    "    optimizer=keras.optimizers.Adam(lr=1e-3),\n",
    "    loss=keras.losses.mse,\n",
    "    metrics=[\"acc\"],\n",
    ")\n",
    "\n",
    "epochs = 10\n",
    "history = model.fit(train_flow, epochs=epochs, validation_data=test_flow)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "executionInfo": {
     "elapsed": 9222,
     "status": "ok",
     "timestamp": 1615732391007,
     "user": {
      "displayName": "Aldo Marzullo",
      "photoUrl": "https://lh3.googleusercontent.com/a-/AOh14GjBD_mZewcZ8LCqkD20Nku4DR5OCGFqYkxawoUjgg=s64",
      "userId": "17245895923239449231"
     },
     "user_tz": -60
    },
    "id": "ypxwoPvL83Rr",
    "outputId": "76fe25d5-e08e-4d25-aae1-9a30c382455a"
   },
   "outputs": [],
   "source": [
    "from sklearn import metrics \n",
    "y_pred = np.round(model.predict(train_flow)).flatten()\n",
    "print('Precision:', metrics.precision_score(labels_train, y_pred)) \n",
    "print('Recall:', metrics.recall_score(labels_train, y_pred)) \n",
    "print('F1-Score:', metrics.f1_score(labels_train, y_pred)) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "executionInfo": {
     "elapsed": 8271,
     "status": "ok",
     "timestamp": 1615732401254,
     "user": {
      "displayName": "Aldo Marzullo",
      "photoUrl": "https://lh3.googleusercontent.com/a-/AOh14GjBD_mZewcZ8LCqkD20Nku4DR5OCGFqYkxawoUjgg=s64",
      "userId": "17245895923239449231"
     },
     "user_tz": -60
    },
    "id": "X8ZcWyByNvO7",
    "outputId": "0b75eda5-1d3c-4d22-e0f7-e777e1d63c58"
   },
   "outputs": [],
   "source": [
    "y_pred = np.round(model.predict(test_flow)).flatten()\n",
    "print('Precision:', metrics.precision_score(labels_test, y_pred)) \n",
    "print('Recall:', metrics.recall_score(labels_test, y_pred)) \n",
    "print('F1-Score:', metrics.f1_score(labels_test, y_pred)) "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "Gd7EaYqVqpjJ"
   },
   "source": [
    "#### Hand crafted features"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "executionInfo": {
     "elapsed": 10866,
     "status": "ok",
     "timestamp": 1616871782934,
     "user": {
      "displayName": "Aldo Marzullo",
      "photoUrl": "https://lh3.googleusercontent.com/a-/AOh14GjBD_mZewcZ8LCqkD20Nku4DR5OCGFqYkxawoUjgg=s64",
      "userId": "17245895923239449231"
     },
     "user_tz": -60
    },
    "id": "hygKSMKPj-HF"
   },
   "outputs": [],
   "source": [
    "import community\n",
    "\n",
    "def get_shortest_path(G,u,v):\n",
    "  \"\"\" return the shortest path length between u,v \n",
    "      in the graph without the edge (u,v) \"\"\"\n",
    "  removed = False\n",
    "  if G.has_edge(u,v):\n",
    "    removed = True\n",
    "    G.remove_edge(u,v) # temporary remove edge\n",
    "  \n",
    "  try:\n",
    "    sp = len(nx.shortest_path(G, u, v))\n",
    "  except:\n",
    "    sp = 0\n",
    "\n",
    "  if removed:\n",
    "    G.add_edge(u,v) # add back the edge if it was removed\n",
    "\n",
    "  return sp\n",
    "\n",
    "def get_hc_features(G, samples_edges, labels):\n",
    "  # precompute metrics\n",
    "  centralities = nx.degree_centrality(G)\n",
    "  parts = community.best_partition(G)\n",
    "  \n",
    "  feats = []\n",
    "  for (u,v),l in zip(samples_edges, labels):\n",
    "    shortest_path = get_shortest_path(G, u, v)\n",
    "    j_coefficient = next(nx.jaccard_coefficient(G, ebunch=[(u, v)]))[-1]\n",
    "    u_centrality = centralities[u]\n",
    "    v_centrality = centralities[v]\n",
    "    u_community = parts.get(u)\n",
    "    v_community = parts.get(v)\n",
    "    # add the feature vector\n",
    "    feats += [[shortest_path, j_coefficient, u_centrality, v_centrality]]\n",
    "  return feats\n",
    "\n",
    "feat_train = get_hc_features(graph_train, samples_train, labels_train)\n",
    "feat_test = get_hc_features(graph_test, samples_test, labels_test)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "executionInfo": {
     "elapsed": 831,
     "status": "ok",
     "timestamp": 1616871790199,
     "user": {
      "displayName": "Aldo Marzullo",
      "photoUrl": "https://lh3.googleusercontent.com/a-/AOh14GjBD_mZewcZ8LCqkD20Nku4DR5OCGFqYkxawoUjgg=s64",
      "userId": "17245895923239449231"
     },
     "user_tz": -60
    },
    "id": "E5XIoZ53q4_q",
    "outputId": "d0184893-a242-45dd-e9d8-38e6d4b1f3e6"
   },
   "outputs": [],
   "source": [
    "from sklearn.ensemble import RandomForestClassifier \n",
    "from sklearn import metrics \n",
    "\n",
    "rf = RandomForestClassifier(n_estimators=10) \n",
    "rf.fit(feat_train, labels_train); \n",
    " \n",
    "y_pred = rf.predict(feat_test) \n",
    "print('Precision:', metrics.precision_score(labels_test, y_pred)) \n",
    "print('Recall:', metrics.recall_score(labels_test, y_pred)) \n",
    "print('F1-Score:', metrics.f1_score(labels_test, y_pred)) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "id": "O1YkgCx5rh25"
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "accelerator": "GPU",
  "colab": {
   "authorship_tag": "ABX9TyNqI0nb+1UIx1QCpehAMWm6",
   "collapsed_sections": [],
   "name": "socialNetwork.ipynb",
   "provenance": []
  },
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.5.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}
